/**
 * 
 */
package com.gwcloud.leetcode.hot100;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName   : Leetcode0076 
 * @author      : ganwei 
 * @date        : 2020年5月18日
 * @Description : Leetcode0076 最小覆盖子串
 */
public class Leetcode0076 {
    /**
     * -解题思路,滑窗算法
     */
	public String minWindow(String s, String t) {
    	int start = 0, minLen = Integer.MAX_VALUE;
    	int left = 0, right = 0;
    	
    	Map<Character, Integer> window = new HashMap<Character, Integer>();
    	Map<Character, Integer> needs = new HashMap<Character, Integer>();
    	
    	for(int i = 0; i < t.length(); i++){
    		int count = needs.getOrDefault(t.charAt(i), 0);
    		needs.put(t.charAt(i), count + 1);
    	}
    	
    	int match = 0;
    	
    	while(right < s.length()){
    		char c = s.charAt(right);
    		int count = window.getOrDefault(c, 0);
    		window.put(c, count + 1);
    		
    		if(needs.containsKey(c) && window.get(c).intValue() == needs.get(c).intValue()){
    			match++;
    		}
    		
    		while(left <= right && match == needs.size()){
    			c = s.charAt(left);
    			if(minLen > right-left+1){
    				start = left;
    				minLen = right - left + 1;
    			}
    			window.put(c, window.get(c)-1);
    			if(needs.containsKey(c) && window.get(c).intValue() < needs.get(c).intValue())
    			{
    				match--;
    			}
    			left++;
    		}
    		right++;
    	}
    	
		if(minLen == Integer.MAX_VALUE){
			return "";
		}else{
			return s.substring(start,start + minLen + 1);
		}
    }
    /**
     * 主函数
     */
    public static void main(String[] args){
    	
    }
}
